//https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
//https://www.bilibili.com/video/BV1mG4y1A7Gu/?vd_source=4ec910f05eea76e8fe7255f381962332
#include <string>
#include <vector>
#include <set>
#include <iostream>
#include <functional>

using namespace std;

class Solution {
    string MAPPING[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public:
    vector<string> letterCombinations(string digits) {
        int n = digits.length();
        if (n == 0) return {};
        vector<string> ans;
        string path(n, 0); // 本题 path 长度固定为 n
        function<void(int)> dfs = [&](int i) {
            if (i == n) {
                ans.emplace_back(path);
                return;
            }
            for (char c : MAPPING[digits[i] - '0']) {
                path[i] = c; // 直接覆盖
                dfs(i + 1);
            }
        };
        dfs(0);
        return ans;
    }
};

class Solution {
public:
    std::vector<string> res;
    void dfs(std::vector<string>& v,int index,int size,std::string str){
        if(index==size){
            std::cout << str<< std::endl;
            res.emplace_back(str);
            return;
        }
        for(auto c:v[index]){
            str.push_back(c);
            dfs(v,index+1,size,str);
            str.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return {};
        string MAPPING[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        std::vector<string> vec_str{};
        for(auto d:digits){
            int i=d-'0';
            vec_str.emplace_back(MAPPING[i]);
        }
        dfs(vec_str,0,digits.size(),"");
        return res;
    }
};